package com.wellsfargo.bm;

public class BitOperator {

	public long divide(long x, long y){
		
		boolean isNegative=false;
		if(x<0){
			isNegative=!isNegative;
			x=-x;
		}
		if(y<0){
			isNegative=!isNegative;
			y=-y;
		}
		if(x<y || x==0)
			return 0;
		//
		long tempY=y;
		while(tempY<x){
			tempY=tempY<<1;
		}
		
		//start
		long rem=x;
		long quotient=0;
		while(true){
			if(tempY<=rem){
				quotient=quotient<<1;
				quotient=quotient|1;
				rem=rem-tempY;
				if(rem<y)
					break;
			}
			else if(tempY>rem){
				quotient=quotient<<1;
			}
			tempY=tempY>>1;
		}
		while(tempY>y){
			quotient=quotient<<1;
			tempY=tempY>>1;
		}
		if(isNegative)
			return -quotient;
		return quotient;
	}
	
	public long add(long x, long y){
		long carry=0;
		for(int i=0;i<62;i++){
			if((((x>>i) & (y>>i)) | ((x>>i) & (carry>>i)) | ((carry>>i) & (y>>i)))==1){
				carry=carry|(1<<(i+1));
			}
		}
		return carry^x^y;
	}
	
	public double findroot(double n){
		double x=n;
		double y=1;
		
		while(x-y>0.01){
			x=(4*x+y)/5;
			y=n/x;
		}
		System.out.println(x);
		return x;
	}
	
	public boolean isMatch(String input, String pattern, int inputInd, int pInd){
		//edge cases
		
		if(inputInd==input.length() && pInd==pattern.length())
			return true;
		if(inputInd>=input.length() || pInd>=pattern.length())
			return false;
		
		//main code
		if(pInd==pattern.length()-1 || pattern.charAt(pInd+1)!='*'){
			if(pattern.charAt(pInd)==input.charAt(inputInd))
				return isMatch(input,pattern,inputInd+1, pInd+1);
			return false;
		}
		else{
			int i=0;
			while((pattern.charAt(pInd)=='.'|| pattern.charAt(pInd)==input.charAt(inputInd)) && inputInd+i <=input.length()){
				if(isMatch(input, pattern, inputInd+i,pInd+2))
					return true;
				i++;
			}
		}
		return isMatch(input, pattern, inputInd,pInd+2);
	}

}
